package leetcode.editor.cn.q1_300.q250;
//你和你的朋友，两个人一起玩 Nim 游戏： 
//
// 
// 桌子上有一堆石头。 
// 你们轮流进行自己的回合， 你作为先手 。 
// 每一回合，轮到的人拿掉 1 - 3 块石头。 
// 拿掉最后一块石头的人就是获胜者。 
// 
//
// 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。 
//
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：false 
//解释：以下是可能的结果:
//1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
//2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
//3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
//在所有结果中，你的朋友是赢家。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：n = 2
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
//
// 👍 686 👎 0

/**
 * 思路：
 * 动态规划，规律为：只要给对手剩下 4 块石头，自己肯定会赢（4 块石头对手不论怎么拿，都会赢），如果剩下 1-3 块石头，自己就会输
 * <p>
 * 其他的情况，都能转为 1-4 块石头的情况。如 5 块石头，为了自己能赢，就要给对手剩下 4 块，也就是只要拿 1 块就可以
 * 即，在两个人每一步都是最优解的情况下，石头数量就决定了谁能赢，能拿到最后一块石头，说明给对手剩下了 4 块石头，也就是说第 n-4 块石头也是自己拿到的
 * <p>
 * n 的状态完全由 n-4 决定。
 * <p>
 * 而前 4 次的状态一定为 T T T F，根据这 4 个状态就可以推断出后续状态， n = n-4
 * 最后的数组通过观察可以发现，只要是 4 的倍数，那就是 false，其他为 true
 */
public class Q292_NimGame {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canWinNim(int n) {
            return n % 4 != 0;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q292_NimGame().new Solution();
        // TO TEST
        System.out.println(solution.canWinNim(7));
    }
}